import collections
from typing import List


class Solution:
    def minMalwareSpread(self, graph: List[List[int]], initial: List[int]) -> int:
        size = len(graph)

        ans = []

        for n in initial:
            visited = set(initial) - {n}
            queue = collections.deque(visited)
            while queue:
                i = queue.popleft()
                for j in range(size):
                    if graph[i][j] == 1 and j != n:
                        if j not in visited:
                            visited.add(j)
                            queue.append(j)
            ans.append((len(visited), n))

        ans.sort()

        return ans[0][1]


if __name__ == "__main__":
    # 0
    print(Solution().minMalwareSpread(graph=[[1, 1, 0], [1, 1, 0], [0, 0, 1]], initial=[0, 1]))

    # 1
    print(Solution().minMalwareSpread(graph=[[1, 1, 0], [1, 1, 1], [0, 1, 1]], initial=[0, 1]))

    # 1
    print(Solution().minMalwareSpread(graph=[[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 1], [0, 0, 1, 1]], initial=[0, 1]))
